package leetcode.year2021.month10;

public class _15_01Trap42 {
  // 42. 接雨水

  public static void main(String[] args) {
    int[] input = new int[]{4,2,0,3,2,5};
    int[] input1 = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
    int ans = trap(input);
    System.out.println(ans);
  }

  // 思路： 找到每一个凹槽, 我的写法有问题，使用双指针求值

  public static int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
      if (height[left] < height[right]) {
        if (height[left] >= left_max) {
          left_max = height[left];
        } else {
          ans += (left_max - height[left]);
        }
        ++left;
      } else {
        if (height[right] >= right_max) {
          right_max = height[right];
        } else {
          ans += (right_max - height[right]);
        }
        --right;
      }
    }
    return ans;
  }

//  public int trap(int[] height) {
//    int ans = 0;
//    int left = 0, right = height.length - 1;
//    int leftMax = 0, rightMax = 0;
//    while (left < right) {
//      leftMax = Math.max(leftMax, height[left]);
//      rightMax = Math.max(rightMax, height[right]);
//      if (height[left] < height[right]) {
//        ans += leftMax - height[left];
//        ++left;
//      } else {
//        ans += rightMax - height[right];
//        --right;
//      }
//    }
//    return ans;
//  }

//    int sum = 0;
//    if (height.length < 3){
//      return sum;
//    }
//    int left = 0;
//    int right = 0;
//    while (right < height.length-1 && height[right] <= height[right+1]){
//      right++;
//    }
//    left = right;
//
//    while (right < height.length){
//      right = getNextGroovy(height,right);
//      int level = Math.min(height[left],height[right]);
//      sum += getNextGroovyArea(height,left,right,level);
//      left = right;
//
//      if (right == height.length - 1){
//        break;
//      }
//    }
//
//    return sum;
//  }
//
//  private static int getNextGroovyArea(int[] height, int left, int right, int level) {
//    int tempSum = 0;
//    for (int i = left+1; i < right; i++) {
//      if (level - height[i] > 0){
//        tempSum += level - height[i];
//      }
//    }
//    return tempSum;
//  }
//
//  private static int getNextGroovy(int[] height, int right) {
//    while (right < height.length-1 && height[right] >= height[right+1]) {
//      right++;
//    }
//    while (right < height.length-1 && height[right] <= height[right+1]) {
//      right++;
//    }
//    return right;
//  }

  /**
   * 42. 接雨水
   * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
   *
   * 示例 1：
   *
   * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
   * 输出：6
   * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
   * 示例 2：
   *
   * 输入：height = [4,2,0,3,2,5]
   * 输出：9
   *
   * 提示：
   *
   * n == height.length
   * 1 <= n <= 2 * 104
   * 0 <= height[i] <= 105
   */
}
